374 - Big mod/p374.cpp

   1 #include <iostream>
   2 #include <limits.h>
   3 using namespace std;
   4
   5
   6 //retorna (b^p)mod(m)
   7 // 0 <= b,p <= 2147483647
   8 // 1 <= m <= 46340
   9 long f(long b, long p, long m){
  10   long mask = 1;
  11   long pow2 = b % m;
  12   long r = 1;
  13
  14   while (mask){
  15     if (p & mask)
  16       r = (r * pow2) % m;
  17     pow2 = (pow2*pow2) % m;
  18     mask <<= 1;
  19   }
  20   return r;
  21 }
  22
  23 int main(){
  24   long b, p, m;
  25   while (cin >> b >> p >> m){
  26     cout << f(b, p, m) << endl;
  27   }
  28   return 0;
  29 }